package com.algorithm;

/**
 * 反转链表
 * 题目：输入一个链表，反转链表后，输出新链表的表头
 * 思路：牛客网 官方题解思路
 * 初始化：3个指针
 * 1）pre指针指向已经反转好的链表的最后一个节点，最开始没有反转，所以指向nullptr
 * 2）cur指针指向待反转链表的第一个节点，最开始第一个节点待反转，所以指向head
 * 3）nex指针指向待反转链表的第二个节点，目的是保存链表，因为cur改变指向后，后面的链表则失效了，所以需要保存
 * 接下来，循环执行以下三个操作
 * 1）nex = cur->next, 保存作用
 * 2）cur->next = pre 未反转链表的第一个节点的下个指针指向已反转链表的最后一个节点
 * 3）pre = cur， cur = nex; 指针后移，操作下一个未反转链表的第一个节点
 */
public class ReverseList {

    public static void main(String[] args) {
        int a=0;
    }
    public static ListNode reverseList(ListNode head) {
        ListNode cur=head;
        ListNode pre =null;
        ListNode next=null;
        while(cur!=null){
            next=cur.next;
            cur.next=pre;
            pre =cur;
            cur=next;
        }
        return pre;
    }
}
